#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.


class PowerRemainder:
    def power_remainder(self, num, power, divisor):
        # return num^power % divisor
        self.num = num % divisor      # num 和 (num % divisor)效果相同
        self.power = power
        self.divisor = divisor
        return self.power_rec(power)

    def power_rec(self, power):
        if power == 1:
            # 递归边界
            return self.num

        half = power // 2
        half_result = self.power_rec(half)

        even_result = (half_result * half_result) % self.divisor
        if power % 2 == 0:
            return even_result
        else:
            return (even_result * self.num)  % self.divisor


def main():
    print("start main")
    power = PowerRemainder()
    # v = power.power_remainder(2, 3, 11)
    v = power.power_remainder(2, 65, 11)        # 2^65 % 11
    print(v)


if __name__ == "__main__":
    main()
